package main.leetcode.clockin.April;

import main.datastruc.ListNode;

import java.util.Stack;

/**
 * 445.两数相加II
 *
 * <p>给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
 *
 * <p>你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 *
 * <p>
 *
 * <p>进阶：如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
 *
 * <p>
 *
 * <p>示例：输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 8 -> 0 -> 7
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/add-two-numbers-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day14 {
    public static void main(String[] args) {
        ListNode l1 = ListNode.creList(new int[] {3, 9, 9, 9, 9, 9, 9, 9, 9, 9});
        ListNode l2 = ListNode.creList(new int[] {7});
        System.out.println(new day14().addTwoNumbers(l1, l2));
    }

    //    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    //        Stack<Integer> stack1 = new Stack<>();
    //        Stack<Integer> stack2 = new Stack<>();
    //        ListNode node = l1;
    //        while (node != null) {
    //            stack1.push(node.val);
    //            node = node.next;
    //        }
    //        node = l2;
    //        while (node != null) {
    //            stack2.push(node.val);
    //            node = node.next;
    //        }
    //        ListNode head = new ListNode(0);
    //        int tmp, carry = 0;
    //        while (!stack1.isEmpty() || !stack2.isEmpty()) {
    //            if (stack1.isEmpty()) tmp = stack2.pop() + carry;
    //            else if (stack2.isEmpty()) tmp = stack1.pop() + carry;
    //            else tmp = stack1.pop() + stack2.pop() + carry;
    //            if (tmp > 9) {
    //                node = new ListNode(tmp % 10);
    //                carry = 1;
    //            } else {
    //                node = new ListNode(tmp);
    //                carry = 0;
    //            }
    //            node.next = head.next;
    //            head.next = node;
    //        }
    //        if (carry > 0) {
    //            node = new ListNode(carry);
    //            node.next = head.next;
    //            head.next = node;
    //        }
    //        return head.next;
    //    }

    // 优化
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        ListNode node = l1;
        while (node != null) {
            stack1.push(node.val);
            node = node.next;
        }
        node = l2;
        while (node != null) {
            stack2.push(node.val);
            node = node.next;
        }
        ListNode head = new ListNode(-1);
        int cur = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty() || cur > 0) {
            if (!stack1.isEmpty()) cur += stack1.pop();
            if (!stack2.isEmpty()) cur += stack2.pop();
            node = new ListNode(cur % 10);
            node.next = head.next;
            head.next = node;
            cur /= 10;
        }

        return head.next;
    }
}
